//给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 
//
// k 是一个正整数，它的值小于或等于链表的长度。 
//
// 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 
//
// 进阶： 
//
// 
// 你可以设计一个只使用常数额外空间的算法来解决此问题吗？ 
// 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], k = 2
//输出：[2,1,4,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1,2,3,4,5], k = 3
//输出：[3,2,1,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2,3,4,5], k = 1
//输出：[1,2,3,4,5]
// 
//
// 示例 4： 
//
// 
//输入：head = [1], k = 1
//输出：[1]
// 
//
// 
// 
//
// 提示： 
//
// 
// 列表中节点的数量在范围 sz 内 
// 1 <= sz <= 5000 
// 0 <= Node.val <= 1000 
// 1 <= k <= sz 
// 
// Related Topics 递归 链表 
// 👍 1460 👎 0


package leetcode.editor.cn.lc25;

public class ReverseNodesInKGroup {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode n1 = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4,new ListNode(5)))));
        ListNode head = solution.reverseKGroup(n1, 2);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }
}
//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head==null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(0,head);
        ListNode preTail = dummy;

        ListNode secStart, secEnd, nextSecHead = head;

        outer:
        while (nextSecHead != null) {
            secStart = nextSecHead;
            secEnd = secStart;
            for (int i = 1; i < k; i++) {
                secEnd = secEnd.next;
                if (secEnd == null) {
                    break outer;
                }
            }

            // 下一段开始
            nextSecHead = secEnd.next;
            // reverse start,end
            // pt -> || s1 -> s2 -> ... si ->  ||  nh
            // pt -> || si -> s(i-1) -> ... s1 ->  ||  nh

            ListNode newHead1 = reverseSection(secStart, nextSecHead);
            secStart.next = nextSecHead;
            preTail.next = newHead1;
            preTail = secStart;
        }

        return dummy.next;

    }


    static ListNode reverseSection(ListNode head, ListNode nextHead) {
        ListNode p=head;
        ListNode s = head.next;
        ListNode tmp;
        while (s != nextHead) {
            tmp = s.next;
            s.next = p;
            p=s;
            s = tmp;
        }
        return p;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "{" + val +
                "} -> " +
                (next == null ? "" : next.toString());
    }
}